package algorithms.leecode;

public class Au74 {
    public static void main(String[] args) {
        new Au74().searchMatrix(new int[][]{{-10},{-7},{-5}},-10);
    }
    public boolean searchMatrix(int[][] matrix, int target) {
        int li = findIndex(matrix,target);
        if (matrix[li][0] > target) {
             return false;
        }
        int[] arr = matrix[li];
        int start = 0;
        int end = arr.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (arr[mid] > target) {
                end = mid - 1;
            } else if (arr[mid] < target) {
                start = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }
    public int findIndex(int[][] matrix,int target){
        int start = 0;
        int end = matrix.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (matrix[mid][0] > target) {
                end = mid - 1;
            } else if (matrix[mid][0] <= target) {
                if (mid == matrix.length - 1) {
                    return mid;
                }
                if (matrix[mid + 1][0] > target) {
                    return mid;
                }
                start = mid + 1;
            }

        }
        return start;

    }
}
